SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Pathfinding</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Pathfinding</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">For other uses, see <a href="Pathfinder_(disambiguation)" class="mw-redirect mw-disambig" title="Pathfinder (disambiguation)">Pathfinder (disambiguation)</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1248332772">

/* start https://en.wikipedia.org/ */

.mw-parser-output .multiple-issues-text{width:95%;margin:0.2em 0}.mw-parser-output .multiple-issues-text>.mw-collapsible-content{margin-top:0.3em}.mw-parser-output .compact-ambox .ambox{border:none;border-collapse:collapse;background-color:transparent;margin:0 0 0 1.6em!important;padding:0!important;width:auto;display:block}body.mediawiki .mw-parser-output .compact-ambox .ambox.mbox-small-left{font-size:100%;width:auto;margin:0}.mw-parser-output .compact-ambox .ambox .mbox-text{padding:0!important;margin:0!important}.mw-parser-output .compact-ambox .ambox .mbox-text-span{display:list-item;line-height:1.5em;list-style-type:disc}body.skin-minerva .mw-parser-output .multiple-issues-text>.mw-collapsible-toggle,.mw-parser-output .compact-ambox .ambox .mbox-image,.mw-parser-output .compact-ambox .ambox .mbox-imageright,.mw-parser-output .compact-ambox .ambox .mbox-empty-cell,.mw-parser-output .compact-ambox .hide-when-compact{display:none}

/* end https://en.wikipedia.org/ */

</style>

<p><b>Pathfinding</b> or <b>pathing</b> is the search, by a computer application, for the shortest route between two points. It is a more practical variant on <a href="Maze-solving_algorithm" title="Maze-solving algorithm">solving mazes</a>. This field of research is based heavily on <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a> for finding the shortest path on a <a href="Glossary_of_graph_theory#Weighted_graphs_and_networks" title="Glossary of graph theory">weighted graph</a>.

</p><p>Pathfinding is closely related to the <a href="Shortest_path_problem" title="Shortest path problem">shortest path problem</a>, within <a href="Graph_theory" title="Graph theory">graph theory</a>, which examines how to identify the path that best meets some criteria (shortest, cheapest, fastest, etc) between two points in a large network.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<p>At its core, a pathfinding method searches a <a href="Graph_(data_structure)" class="mw-redirect" title="Graph (data structure)">graph</a> by starting at one <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertex</a> and exploring adjacent <a href="Node_(computer_science)" title="Node (computer science)">nodes</a> until the destination node is reached, generally with the intent of finding the cheapest route. Although graph searching methods such as a <a href="Breadth-first_search" title="Breadth-first search">breadth-first search</a> would find a route if given enough time, other methods, which "explore" the graph, would tend to reach the destination sooner. An analogy would be a person walking across a room; rather than examining every possible route in advance, the person would generally walk in the direction of the destination and only deviate from the path to avoid an obstruction, and make deviations as minor as possible.

</p><p>Two primary problems of pathfinding are (1) to find a path between two nodes in a <a href="Graph_(data_structure)" class="mw-redirect" title="Graph (data structure)">graph</a>; and (2) the <a href="Shortest_path_problem" title="Shortest path problem">shortest path problem</a>—to find the <a href="Shortest_path_problem" title="Shortest path problem">optimal shortest path</a>. Basic algorithms such as <a href="Breadth-first_search" title="Breadth-first search">breadth-first</a> and <a href="Depth-first_search" title="Depth-first search">depth-first</a> search address the first problem by <a href="Brute-force_search" title="Brute-force search">exhausting</a> all possibilities; starting from the given node, they iterate over all potential paths until they reach the destination node. These algorithms run in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V|+|E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V|+|E|)}</annotation>

</semantics>

</math></span><img src="./a7cf317fbe3965ae3164f28c1f6858696adb23f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.573ex; height:2.843ex;" alt="{\displaystyle O(|V|+|E|)}" loading="lazy"></span>, or linear time, where V is the number of vertices, and E is the number of <a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a> between vertices.

</p><p>The more complicated problem is finding the optimal path. The exhaustive approach in this case is known as the <a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford algorithm</a>, which yields a time complexity of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|V||E|)}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|V||E|)}</annotation>

</semantics>

</math></span><img src="./2d81aded51fae699d4f659fee1faa684233ab581.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.733ex; height:2.843ex;" alt="{\displaystyle O(|V||E|)}" loading="lazy"></span>, or quadratic time. However, it is not necessary to examine all possible paths to find the optimal one. Algorithms such as <a href="A*_search_algorithm" title="A* search algorithm">A*</a> and <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a> strategically eliminate paths, either through <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">heuristics</a> or through <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a>. By eliminating impossible paths, these algorithms can achieve time complexities as low as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(|E|\log(|V|))}">

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(|E|\log(|V|))}</annotation>

</semantics>

</math></span><img src="./41ef1a141ec77d4f658a1af550a645f39cbbd897.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.901ex; height:2.843ex;" alt="{\displaystyle O(|E|\log(|V|))}" loading="lazy"></span>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>The above algorithms are among the best general algorithms which operate on a graph without preprocessing. However, in practical travel-routing systems, even better time complexities can be attained by algorithms which can pre-process the graph to attain better performance.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> One such algorithm is <a href="Contraction_hierarchies" title="Contraction hierarchies">contraction hierarchies</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Dijkstra's_algorithm">Dijkstra's algorithm</h3></div>

<p>A common example of a graph-based pathfinding algorithm is <a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> This algorithm begins with a start node and an "open set" of candidate nodes. At each step, the node in the open set with the lowest distance from the start is examined. The node is marked "closed", and all nodes adjacent to it are added to the open set if they have not already been examined. This process repeats until a path to the destination has been found. Since the lowest distance nodes are examined first, the first time the destination is found, the path to it will be the shortest path.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

</p><p>Dijkstra's algorithm fails if there is a negative <a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edge</a> weight. In the hypothetical situation where Nodes A, B, and C form a connected undirected graph with edges AB = 3, AC = 4, and BC = −2, the optimal path from A to C costs 1, and the optimal path from A to B costs 2. Dijkstra's Algorithm starting from A will first examine B, as that is the closest. It will assign a cost of 3 to it, and mark it closed, meaning that its cost will never be reevaluated. Therefore, Dijkstra's cannot evaluate negative edge weights. However, since for many practical purposes there will never be a negative edgeweight, Dijkstra's algorithm is largely suitable for the purpose of pathfinding.

</p>

<div class="mw-heading mw-heading3"><h3 id="A*_algorithm">A* algorithm</h3></div>

<p><a href="A*_search_algorithm" title="A* search algorithm">A*</a> is a variant of Dijkstra's algorithm with a wide variety of use cases. A* assigns a weight to each open node equal to the weight of the edge to that node plus the approximate distance between that node and the finish. This approximate distance is found by the <a href="Heuristic_(computer_science)" title="Heuristic (computer science)">heuristic</a>, and represents a minimum possible distance between that node and the end. This allows it to eliminate longer paths once an initial path is found. If there is a path of length x between the start and finish, and the minimum distance between a node and the finish is greater than x, that node need not be examined.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>A* uses this heuristic to improve on the behavior relative to Dijkstra's algorithm. When the heuristic evaluates to zero, A* is equivalent to Dijkstra's algorithm. As the heuristic estimate increases and gets closer to the true distance, A* continues to find optimal paths, but runs faster (by virtue of examining fewer nodes). When the value of the heuristic is exactly the true distance, A* examines the fewest nodes. (However, it is generally impractical to write a heuristic function that always computes the true distance, as the same comparison result can often be reached using simpler calculations – for example, using <a href="Chebyshev_distance" title="Chebyshev distance">Chebyshev distance</a> over <a href="Euclidean_distance" title="Euclidean distance">Euclidean distance</a> in <a href="Plane_(mathematics)" title="Plane (mathematics)">two-dimensional space</a>.) As the value of the heuristic increases, A* examines fewer nodes but no longer guarantees an optimal path. In many applications (such as video games) this is acceptable and even desirable, in order to keep the algorithm running quickly.

</p>

<div class="mw-heading mw-heading2"><h2 id="In_video_games">In video games</h2></div>

<p>Pathfinding has a history of being included in video games with moving objects or NPCs. <a href="Chris_Crawford_(game_designer)" title="Chris Crawford (game designer)">Chris Crawford</a> in 1982 described how he "expended a great deal of time" trying to solve a problem with pathfinding in <i><a href="Tanktics" class="mw-redirect" title="Tanktics">Tanktics</a></i>, in which computer tanks became trapped on land within U-shaped lakes. "After much wasted effort I discovered a better solution: delete U-shaped lakes from the map", he said.<sup id="cite_ref-crawford198212_6-0" class="reference"><a href="#cite_note-crawford198212-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p><p><br>

</p>

<div class="mw-heading mw-heading3"><h3 id="Hierarchical_path_finding">Hierarchical path finding</h3></div>

<p>The concept of hierarchical pathfinding predates its adoption by the <a href="Video_game_industry" title="Video game industry">video game industry</a> and has its roots in classical artificial intelligence research. One of the earliest formal descriptions appears in Sacerdoti's work on ABSTRIPS (Abstraction-Based <a href="Stanford_Research_Institute_Problem_Solver" title="Stanford Research Institute Problem Solver">STRIPS</a>) in 1974,<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> which explored hierarchical search strategies in logic-based planning. Later research, such as Hierarchical A* by Holte et al., further developed the theory of abstraction hierarchies in search problems.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>In the context of video games, the need for efficient planning on large maps with limited <a href="CPU_time" title="CPU time">CPU time</a> led to the practical implementation of hierarchical pathfinding algorithms. A notable advancement was the introduction of Hierarchical Path-Finding A* (HPA*) by Botea et al. in 2004.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> HPA* partitions the map into clusters and precomputes optimal local paths between entrance points of adjacent clusters. At runtime, it plans an abstract path through the cluster graph, then refines that path within each cluster. This significantly reduces the search space and allows for near-optimal planning with much faster performance.

</p><p>Partial-Refinement A* (PRA*), developed by Sturtevant and Buro, takes a similar approach but emphasizes interleaved planning and acting. Instead of refining the entire path immediately, PRA* refines only the first few steps and continues refining the rest as needed during execution. This is especially useful in dynamic environments.

</p><p>Similar techniques include <a href="Navigation_mesh" title="Navigation mesh">navigation meshes</a> (navmesh), used for geometric planning in games, and multimodal <a href="Transportation_planning" title="Transportation planning">transportation planning</a>, such as in variations of the <a href="Travelling_salesman_problem" title="Travelling salesman problem">travelling salesman problem</a> that involve multiple transport types.

</p><p>A hierarchical planner performs pathfinding in two phases: first, between clusters at a high level; then, within individual clusters at a low level.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> This structure enables <a href="Guided_local_search" title="Guided local search">guided local search</a> with fewer <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">nodes</a>, resulting in high performance. The main drawback is the implementation complexity of maintaining abstraction layers and refinements.

</p>

<div class="mw-heading mw-heading4"><h4 id="Example">Example</h4></div>

<p>A <a href="Mini-map" title="Mini-map">map</a> with a size of 3000×2000 nodes contains 6 million tiles. Planning a path directly on this scale, even with an optimized <a href="Algorithm" title="Algorithm">algorithm</a>, is computationally intensive due to the vast number of graph nodes and possible paths. A hierarchical approach divides the map into 300×200 node clusters, forming a 10×10 grid (100 clusters total). The high-level abstract graph now contains only 100 nodes. A path is planned between these clusters, which is computationally cheap. Once the abstract path is found, each cluster on the path is processed using a regular <a href="A*_search_algorithm" title="A* search algorithm">A* planner</a> to find the exact low-level route within. This two-stage process significantly improves efficiency while maintaining near-optimal path quality.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithms_used_in_pathfinding">Algorithms used in pathfinding</h2></div>

<ul><li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's algorithm</a></li>

<li><a href="A*_search_algorithm" title="A* search algorithm">A* search algorithm</a>, a special case of the Dijkstra's algorithm</li>

<li><a href="D*" title="D*">D*</a> a family of <a href="Incremental_heuristic_search" title="Incremental heuristic search">incremental heuristic search</a> algorithms for problems in which constraints vary over time or are not completely known when the <a href="Intelligent_agent" title="Intelligent agent">agent</a> first plans its path</li>

<li><a href="Any-angle_path_planning" title="Any-angle path planning">Any-angle path planning</a> algorithms, a family of algorithms for planning paths that are not restricted to move along the edges in the search graph, designed to be able to take on any angle and thus find shorter and straighter paths</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Multi-agent_pathfinding">Multi-agent pathfinding</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Multi-agent_pathfinding" title="Multi-agent pathfinding">Multi-agent pathfinding</a></div>

<p>Multi-agent pathfinding is to find the paths for multiple agents from their current locations to their target locations without colliding with each other, while at the same time optimizing a cost function, such as the sum of the path lengths of all agents. It is a generalization of pathfinding. Many multi-agent pathfinding algorithms are generalized from A*, or based on reduction to other well studied problems such as integer linear programming.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> However, such algorithms are typically incomplete; in other words, not proven to produce a solution within polynomial time. Some parallel approaches, such as <a href="Collaborative_diffusion" title="Collaborative diffusion">Collaborative Diffusion</a>, are based on <a href="Embarrassingly_parallel" title="Embarrassingly parallel">embarrassingly parallel</a> algorithms spreading multi-agent pathfinding into computational grid structures, e.g., cells similar to <a href="Cellular_automata" class="mw-redirect" title="Cellular automata">cellular automata</a>. A different category of algorithms sacrifice optimality for performance by either making use of known navigation patterns (such as traffic flow) or the topology of the problem space.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Motion_planning" title="Motion planning">Motion planning</a></li>

<li><a href="Any-angle_path_planning" title="Any-angle path planning">Any-angle path planning</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20160304025622/http://lcm.csa.iisc.ernet.in/dsa/node162.html">"7.2.1 Single Source Shortest Paths Problem: Dijkstra's Algorithm"</a>. Archived from <a rel="nofollow" class="external text" href="http://lcm.csa.iisc.ernet.in/dsa/node162.html">the original</a> on 2016-03-04<span class="reference-accessdate">. Retrieved <span class="nowrap">2012-05-18</span></span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFDellingSandersSchultesWagner2009" class="citation book cs1">Delling, D.; <a href="Peter_Sanders_(computer_scientist)" title="Peter Sanders (computer scientist)">Sanders, P.</a>; Schultes, D.; <a href="Dorothea_Wagner" title="Dorothea Wagner">Wagner, D.</a> (2009). "Engineering route planning algorithms". <i>Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation</i>. Lecture Notes in Computer Science. Vol. 5515. Springer. pp. <span class="nowrap">117–</span>139. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.8916">10.1.1.164.8916</a></span>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-02094-0_7">10.1007/978-3-642-02094-0_7</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-02093-3</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFDijkstra1959" class="citation journal cs1">Dijkstra, E. W. (December 1959). "A note on two problems in connexion with graphs". <i>Numerische Mathematik</i>. <b>1</b> (1): <span class="nowrap">269–</span>271. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01386390">10.1007/BF01386390</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm">"5.7.1 Dijkstra Algorithm"</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.raywenderlich.com/4946/introduction-to-a-pathfinding">"Introduction to A* Pathfinding"</a>.</cite></span>

</li>

<li id="cite_note-crawford198212-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-crawford198212_6-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFCrawford1982" class="citation magazine cs1">Crawford, Chris (December 1982). <a rel="nofollow" class="external text" href="https://archive.org/stream/byte-magazine-1982-12/1982_12_BYTE_07-12_Game_Plan_1982#page/n97/mode/2up">"Design Techniques and Ideas for Computer Games"</a>. <i>BYTE</i>. p. 96<span class="reference-accessdate">. Retrieved <span class="nowrap">19 October</span> 2013</span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFSacerdoti,_Earl_D1974" class="citation journal cs1">Sacerdoti, Earl D (1974). <a rel="nofollow" class="external text" href="http://elvex.ugr.es/decsai/iaio/doc/1974%20ABSTRIPS.pdf">"Planning in a hierarchy of abstraction spaces"</a> <span class="cs1-format">(PDF)</span>. <i>Artificial Intelligence</i>. <b>5</b> (2): <span class="nowrap">115–</span>135. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0004-3702%2874%2990026-5">10.1016/0004-3702(74)90026-5</a>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFHolte,_Robert_C_and_Perez,_MB_and_Zimmer,_RM_and_MacDonald,_AJ1995" class="citation conference cs1">Holte, Robert C and Perez, MB and Zimmer, RM and MacDonald, AJ (1995). <i>Hierarchical a*</i>. Symposium on Abstraction, Reformulation, and Approximation.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite conference}}</code>: CS1 maint: multiple names: authors list (link)</span></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFBotea,_Adi_and_Muller,_Martin_and_Schaeffer,_Jonathan2004" class="citation journal cs1">Botea, Adi and Muller, Martin and Schaeffer, Jonathan (2004). "Near optimal hierarchical path-finding". <i>Journal of Game Development</i>. <b>1</b>: <span class="nowrap">7–</span>28. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.479.4675">10.1.1.479.4675</a></span>.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)</span></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFPelechano,_Nuria_and_Fuentes,_Carlos2016" class="citation journal cs1">Pelechano, Nuria and Fuentes, Carlos (2016). <a rel="nofollow" class="external text" href="https://upcommons.upc.edu/bitstream/handle/2117/98738/Pelechano_HNAstar_prePrint.pdf">"Hierarchical path-finding for Navigation Meshes (HNA⁎)"</a> <span class="cs1-format">(PDF)</span>. <i>Computers & Graphics</i>. <b>59</b>: <span class="nowrap">68–</span>78. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.cag.2016.05.023">10.1016/j.cag.2016.05.023</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/2117%2F98738">2117/98738</a></span>.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite journal}}</code>: CS1 maint: multiple names: authors list (link)</span></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Hoenig, T. K. Satish Kumar, Tansel Uras, Hong Xu, Craig Tovey, and Guni Sharon. <a rel="nofollow" class="external text" href="https://www.andrew.cmu.edu/user/gswagner/workshop/IJCAI_2016_WOMPF_paper_6.pdf">Overview: generalizations of multi-agent path finding to real-world scenarios.</a> In the 25th International Joint Conference on Artificial Intelligence (IJCAI) Workshop on Multi-Agent Path Finding. 2016.</span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFKhorshid2011" class="citation journal cs1">Khorshid, Mokhtar (2011). <a rel="nofollow" class="external text" href="http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4039/4361">"A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding"</a>. <i>SOCS</i>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external free" href="https://melikpehlivanov.github.io/AlgorithmVisualizer">https://melikpehlivanov.github.io/AlgorithmVisualizer</a></li>

<li><a rel="nofollow" class="external free" href="http://sourceforge.net/projects/argorha">http://sourceforge.net/projects/argorha</a></li>

<li><a rel="nofollow" class="external text" href="https://code.google.com/p/straightedge/">StraightEdge</a> Open Source Java 2D path finding (using A*) and lighting project. Includes applet demos.</li>

<li><a rel="nofollow" class="external text" href="https://github.com/CBCJVM/python-pathfinding">python-pathfinding</a> Open Source Python 2D path finding (using Dijkstra's Algorithm) and lighting project.</li>

<li><a rel="nofollow" class="external text" href="https://code.google.com/p/daedalus-lib/">Daedalus Lib</a> Open Source. Daedalus Lib manages fully dynamic triangulated 2D environment modeling and pathfinding through A* and funnel algorithms.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Graph_and_tree_traversal_algorithms231" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Graph_and_tree_traversal_algorithms231" style="font-size:114%;margin:0 4em"><a href="Graph_traversal" title="Graph traversal">Graph</a> and <a href="Tree_traversal" title="Tree traversal">tree</a> traversal algorithms</div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Graph_traversal" title="Graph traversal">Search</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alpha%E2%80%93beta_pruning" title="Alpha–beta pruning">α–β pruning</a></li>

<li><a href="Best-first_search" title="Best-first search">Best-first search</a></li>

<li><a href="Beam_search" title="Beam search">Beam search</a></li>

<li><a href="Bidirectional_search" title="Bidirectional search">Bidirectional search</a></li>

<li><a href="Breadth-first_search" title="Breadth-first search">Breadth-first search</a>

<ul><li><a href="Lexicographic_breadth-first_search" title="Lexicographic breadth-first search">Lexicographic</a></li>

<li><a href="Parallel_breadth-first_search" title="Parallel breadth-first search">Parallel</a></li></ul></li>

<li><a href="Depth-first_search" title="Depth-first search">Depth-first search</a>

<ul><li><a href="Iterative_deepening_depth-first_search" title="Iterative deepening depth-first search">Iterative deepening</a></li></ul></li>

<li><a href="Fringe_search" title="Fringe search">Fringe search</a></li>

<li><a href="Jump_point_search" title="Jump point search">Jump point search</a></li>

<li><a href="Monte_Carlo_tree_search" title="Monte Carlo tree search">Monte Carlo tree search</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Shortest_path_problem" title="Shortest path problem">Shortest path</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bellman%E2%80%93Ford_algorithm" title="Bellman–Ford algorithm">Bellman–Ford</a></li>

<li><a href="Dijkstra's_algorithm" title="Dijkstra's algorithm">Dijkstra's</a></li>

<li><a href="Floyd%E2%80%93Warshall_algorithm" title="Floyd–Warshall algorithm">Floyd–Warshall</a></li>

<li><a href="Johnson's_algorithm" title="Johnson's algorithm">Johnson's</a></li>

<li><a href="Shortest_path_faster_algorithm" class="mw-redirect" title="Shortest path faster algorithm">Shortest path faster</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Minimum_spanning_tree" title="Minimum spanning tree">Minimum spanning tree</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Bor%C5%AFvka's_algorithm" title="Borůvka's algorithm">Borůvka's</a></li>

<li><a href="Kruskal's_algorithm" title="Kruskal's algorithm">Kruskal's</a></li>

<li><a href="Reverse-delete_algorithm" title="Reverse-delete algorithm">Reverse-delete</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="List_of_algorithms#Graph_search" title="List of algorithms">List of graph search algorithms</a></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-19" href="https://en.wikipedia.org/wiki/?title=Pathfinding&oldid=1286340401">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>